
\documentclass[runningheads,a4paper]{llncs}
\usepackage[margin=1.54in]{geometry}
\usepackage{amssymb,amsmath,authblk}
\setcounter{tocdepth}{3}
\usepackage{graphicx}
\usepackage{tikz}
\usepackage{color}

\usepackage{url}
%\urldef{\mailsa}\path|daniel.smith@nist.gov|
%\urldef{\mailsb}\path|ray.perlner@nist.gov|
%\urldef{\mailsc}\path|dustin.moody@nist.gov|
\newcommand{\keywords}[1]{\par\addvspace\baselineskip
\noindent\keywordname\enspace\ignorespaces#1}


%===============Definitions==========================


\newcommand{\bdf}{\begin{definition}}
\newcommand{\edf}{\end{definition}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\bsp}{\begin{split}}
\newcommand{\esp}{\end{split}}
\newtheorem{Thm}{Theorem}
\newtheorem{Lem}{Lemma}
\newtheorem{Cor}{Corollary}
\newtheorem{Prop}{Proposition}[chapter]
\newtheorem{Def}{Definition}
\newtheorem{Rem}{Remark}
\newcommand{\Z}{\mathbb{Z}}
\def\mathbi#1{\textbf{\em #1}}


%===================End Definitions======================

%===============Perspective Definitions=====================

%\def\xa{108}
%\def\ya{-106}
%\def\za{80}

\def\xdirx{-0.996}
\def\xdiry{0.087}
\def\ydirx{0.614}
\def\ydiry{0.43}
\def\zdirx{0.0}
\def\zdiry{1}

%=============End Perspective Definitions====================

%==============Color Definitions=======================

\definecolor{lightgray}{rgb}{0.85,0.85,0.85}
\definecolor{mediumgray}{rgb}{0.75,0.75,0.75}
\definecolor{darkgray}{rgb}{0.45,0.45,0.45}

%============End Color Definitions======================

%===============Notation Macros=====================

\newcommand\restr[2]{{% we make the whole thing an ordinary symbol
  \left.\kern-\nulldelimiterspace % automatically resize the bar with \right
  #1 % the function
  \vphantom{\big|} % pretend it's a little taller at normal size
  \right|_{#2} % this is the delimiter
  }}

\newcommand{\rkappa}{\raisebox{\depth}{\rotatebox{270}{$\mathcal{K}$}}}

%=============End Notation Macros====================


\begin{document}

\mainmatter

\title{Thermodynamic Analysis of Classical and Quantum Algorithms for Preimage and Collision Search Problems}

\titlerunning{Thermodynamic Analysis of Search Problems}

\toctitle{Lecture Notes in Computer Science}
\tocauthor{Authors' Instructions}
\maketitle

\begin{abstract}
One of the earliest proposed applications of quantum computers was the quadratic speedup of classical brute force search represented by Grover's algorithm. Since then various successor algorithms have been applied to a variety of oracle problems including collision finding and claw finding. Such algorithms have typically been analyzed in terms of query complexity, which is a somewhat unphysical model of the cost of computation in the real world. Other models of these algorithms, such as the quantum circuit model and the quantum random access machine model of computation give more realistic, but sometimes conflicting answers regarding how much advantage the quantum algorithm provides over the corresponding classical algorithm.

We instead adapt Bennett's Brownian model of computation to directly estimate the cost of both classical and quantum operations in terms of time, energy, and memory. We apply this model to compare the best known quantum algorithms for collision search and preimage search to their classical counterparts. In the collision search case, our analysis agrees with previous analysis, based on the gate model of quantum computation, suggesting that quantum computation provides no improvement over the best known classical algorithm. More surprisingly, we find that a Brownian implementation of randomized classical search can achieve the same tradeoffs between time, memory and energy as Grover's algorithm (at least up to logarithmic factors.) This implementation uses thermal noise to drive a random walk within the internal state of a mostly unpowered circuit. 
 
\keywords{Reversible Computation, Quantum Computation, Collision Search, Preimage Search, Grover's algorithm}
\end{abstract}

\section{Introduction}

\section{Bennett's Brownian Computation Model}

In contrast to ballistic models of computation (e.g. \cite{Fredkin1982}), which are generally assumed to be unrealistic, Brownian computers \cite{Bennett1973,Bennett1982} are assumed to operate near thermal equilibrium at a finite temperature, $T$. As in the case of ballistic computers, to avoid being constrained to consume at least $kT ln 2$ energy per bit operation by the Landauer limit \cite{Landauer1961}, the program for a Brownian computer is encoded as a reversible circuit. In the absence of any driving force, the state of the computing system at any given time may be described as a random walk on that circuit, with state transitions that undo a useful computation happening as often as those that perform it. In order for computations to proceed forward at a nonzero expected rate, a driving force, dissipating an energy of $\epsilon$ per gate is imposed. This leads forward transitions within the circuit to occur $e^{\frac{\epsilon}{kT}}$ times more often than backward transitions, resulting in a net forward computation rate proportional to $\frac{\epsilon}{kT}$ for $\epsilon$ small compared to $kT$.

Some additional costs are required in order for Brownian computation to be achieved fault-tolerantly. Energy barriers must be imposed to prevent transitions to physical states outside the reversible circuit, representing the prescribed computation path. In order to suppress the probability of such undesirable transitions so that a circuit of size $G$ can be completed with high probability, the size of these energy barriers must at least be on the order of $kT ln (\frac{kT}{\epsilon}\cdot G).$ Additionally, dissipating a ``latching" energy of about $kT ln (\frac{kT}{\epsilon})$ during the computation's final step is required to suppress backwards transitions once the computation has reached its halting state. These costs are described in detail in \cite{Bennett1982}.

The above costs may, however, be assumed to be negligible in a number of important cases: In particular, the latching energy will be negligible when $\frac{\epsilon}{kT}$ is at least logarithmically more than $\frac{1}{G}$. Additionally, establishing energy barriers to non-computational paths is likely to be a negligible cost when a description of the circuit can be expressed in a physically compact form, for example, using looping constructs. More precisely, if we assume that the circuit can be compressed into a program of size $m_0$, then the cost of imposing energy barriers should be on the order of $m_0\cdot kT ln (\frac{kT}{\epsilon}\cdot G).$ This cost is negligible as long as $\frac{\epsilon}{kT}$ is significantly larger than $e^{-\frac{G}{m_0}}$.

In fact, the initialization cost may be less than this, since it may be more proper to think of the initialization process as rearranging the energy barriers already present in the available raw materials for constructing our computer. The cost is then determined by the Landauer limit and the information content of the circuit, including appropriately large energy barriers. Since the size of these barriers does not need to be precislely specified, but merely bounded above $kT ln (\frac{kT}{\epsilon}\cdot G)$, the information content of the circuit may grow sublogarithmically with $G$. All we can say with confidence is that the information content of the circuit is at least $m_0$, and therefore the initialization energy is at least on the order of $m_0\cdot kT$.

Thus far, we have only given asymptotic scalings for the relation between gate time and per-gate energy, assuming a fixed temperature. However, if we make the heuristic assumption that the rate at which gates are traversed due to Brownian motion is no more than $\frac{h}{4kT}$, following the Margolus-Levitin theorem \cite{Margolus1998}, then we can specify a lower bound, independent of temperature, on the per-gate energy $\epsilon$ required to perform $G$ sequential operations in time $t$: 

\[
\epsilon > \frac{hG}{4t}.
\]

Finally, it is worth commenting on the feasibility of Brownian computation for quantum computers. Brownian computation was originally proposed as a way to improve the thermodynamic efficiency of classical computation. It should be noted that many of the techniques that have been proposed for fault tolerance in quantum compuation are thermodynamically irreversible, in particular, syndrome measurement and magic state preparation. These techniques cannot be used in a Brownian mode of computation. However, there are some proposed techniques, such as the use of Fibonacci anyons for universal quantum computation \cite{AskStevenWhattoCiteHere}, that may be able to achieve fault tolerance without requiring significant thermodynamic irreversibility (although even in such cases, the cost of fault tolerance is believed to be polylogarithmic in the size of the circuit.) We will therefore optimistically assume that quantum operations can be implemented in a Brownian fashion.

We now proceed to analyze the asymptotic complexity of classical and quantum algorithms for collision and preimage search. We will generally ignore logarithmic factors. As we are engaged in asymptotic analysis, units are strictly speaking irrelevant, but assuming natural units (e.g. $c = \hbar = k = 1$) may be desirable to keep constant factors small. 
 
\section{Collision Search}

The best known classical algorithm for finding collisions in a random function is the parallel collision search algorithm of Van Oorschot and Wiener \cite{vanOorschot1999}. If the range of the function is of order $N$, then, given $M$ parallel processes each with memory $O(1)$ the algorithm can find a collision in expected serial depth $O(\frac{\sqrt{N}}{M})$. The communication cost between threads is negligible compared to overall computational costs as long as $M$ is smaller than $\sqrt{N}$ by at least a logarithmic factor.

An improvement over classical collision search has been claimed by Brassard H{\o}yer and Tapp (BHT \cite{Brassard1998}). Their algorithm is a serial process consisting of $O(N^{\frac{1}{3}})$ operations and requires a memory of size $N^{\frac{1}{3}}$. This can be generalized to arbitrary memory size, $M<O(N^{\frac{1}{3}})$, giving a serial complexity of $O\left(\sqrt{\frac{N}{M}}\right)$. The BHT algorithm may be further generalized to a parallel algorithm involving $p$ parallel processors and a shared memory $M$, where $p<M<O\left((Np)^{\frac{1}{3}}\right)$.\footnote{Note this also implies that $M< O\left(\sqrt{N}\right)$. The constraint arises from the requirement that the serial complexity, $O\left(\frac{M}{p}\right)$, of filling a table of size $M$ with oracle values does not exceed the serial complexity $O\left(\sqrt{\frac{N}{Mp}}\right)$ of Grover search.} in this case, the serial complexity is $O\left(\sqrt{\frac{N}{Mp}}\right)$.

Bernstein \cite{bernstein2009cost} has observed that the BHT algorithm, even if parallelized, does not improve upon the Van Oorschot - Wiener algorithm, when measured in terms of memory and serial depth. Since the BHT algorithm also requires $O\left(\sqrt{\frac{N}{M}}\right)$ random access queries to a memory of size $M$, each requiring $O(M)$ gates, it also does not improve upon Van Oorschot Weiner algorithm when evaluated in terms of circuit size and depth (See Beals et al. \cite{beals2013efficient} for a more thorough analysis.) However, BHT does represent an improvement over all classical algorithms in terms of query complexity. Furthermore, the Quantum RAM model of Giovanetti et al. \cite{giovannetti2008quantum} gives a theoretical argument that despite their large gate complexity, quantum memory access operations can be performed at logarithmic energy cost. A question therefore remains whether there exists a physically realistic model of computation where BHT is actually cheaper than the classical algorithms for the same problem. However, if there is such a model, it is not the Brownian model of computation, as we proceed to show:

We first analyze the quantum algorithm, calculating the total energy required to perform a collision search, given a maximum time limit $t$ and a maximum memory size $M$. (Here, we assume, following the quantum RAM model, that the energy complexity of the BHT is dominated by oracle queries rather than memory access): The per operation energy $\epsilon$ scales with the serial complexity divided by $t$, i.e.:

\begin{equation}\label{TBHT}
\epsilon_{quant} = O\left(\frac{\sqrt{\frac{N}{Mp}}}{t}\right). 
\end{equation}
 
The total energy $E$ is then the product of the parallelism, the serial complexity, and the per operation energy, i.e.:

\begin{equation}\label{EBHT}
E_{quant} = O\left(p \cdot \sqrt{\frac{N}{Mp}} \cdot \frac{\sqrt{\frac{N}{Mp}}}{t} \right) = O\left(\frac{N}{Mt} \right).
\end{equation}

Now, we analyze the classical algorithm: The per operation energy again scales with the serial complexity, i.e.:

\begin{equation}\label{TVOW}
\epsilon_{cl} = O\left(\frac{\sqrt{N}}{Mt}\right). 
\end{equation}

The total energy $E$ is again the product of the parallelism (In this case $p = O(M)$), the serial complexity, and the per operation energy, i.e.:

\begin{equation}\label{EVOW}
E_{cl} = O\left( M \cdot \frac{\sqrt{N}}{M} \cdot \frac{\sqrt{N}}{Mt} \right) = O\left(\frac{N}{Mt} \right).
\end{equation}

Thus, even under optimistic assumptions within the Brownian model of computation, we find that quantum computers provide no advantage in terms of energy, memory, or time, for solving the collision search problem.  

\section{Preimage Search}

Grover's algorithm finds preimages in a function with domain size $N$ in serial complexity $O(\sqrt N)$. Grover's algorithm can be generalized to take advantage of $M$ parallel processes each mith memory $O(1)$, in which case the serial complexity is reduced to $O\left(\sqrt{\frac{N}{M}}\right)$. If we impement Grover's algorithm in a Brownian fashion, we find that

\begin{equation}\label{TGrover}
\epsilon_{quant} = O\left(\frac{\sqrt{\frac{N}{M}}}{t} \right),
\end{equation}

and,

\begin{equation}\label{EGrover}
E_{quant} = O\left(M \cdot \sqrt{\frac{N}{M}} \cdot \frac{\sqrt{\frac{N}{M}}}{t} \right) = O\left(\frac{N}{t}\right).
\end{equation}

A na\"ive Brownian implementation for classical search would divide the key space among $M$ parallel processes, each of which would deterministically step through$\frac{N}{M}$ keys searching for the correct one. Such a deterministic classical algorithm would require,

\[
\epsilon_{det} = O\left(\frac{N}{Mt}\right), 
\]

and,

\[
E_{det} = O\left( M \cdot \frac{N}{M} \cdot \frac{N}{Mt} \right) = O\left(\frac{N^2}{Mt} \right).
\]

This already allows us to compete with Grover's algorithm if we allow ourselves a memory of size $O(N).$
%\footnote{This is somewhat unrealistic. We have neglected the initialization cost of memory, and this is only warranted when we can expel waste heat at a temperature $T$ such that
%$\frac{M}{N} < O\left(\sqrt{\frac{kTt}{\hbar}}\right)$. If we use realistic figures, e.g. $t = 1$ year, $T = 300K$, we find that $M$ must be smaller than $N$ by at least a factor of
%$3\times10^{10}$ in order to make the initialization cost negligible, and so the optimal Brownian energy efficiency of the Na\"ive classical algorithm is less than that for Grover's algorithm by
%the same factor. Note however, that if the algorithm is run multiple times in series, it only needs to be initialized once. Additional initializations can be obtained more cheaply by uncomputing.}
However, we can exploit the structure, or rather the lack of structure, of the search problem to improve upon this figure. In particular, rather than deterministically stepping through the keys, dissipating a driving energy each time, we can simply allow Brownian motion to drive the system on a random walk through the keyspace. We will still require a latching energy to end the computation, once the correct key has been found, and an initialization energy to create the necessary energy barriers to prevent unwanted transitions from occuring.

If the search is implemented by $M$ parallel processes, each of size $O(1)$, then each process must reach $\frac{N}{M}$ keys.  This requires the processes to operate at a temperature:

\begin{equation}\label{Tpreimage}
kT = O\left(\frac{N}{Mt}\right).
\end{equation}

The initialization energy should be of order $MkT$ i.e.:

\[
E_{init} = O\left(M \cdot \frac{N}{Mt}\right) =  O\left(\frac{N}{t}\right).
\]

This is identical to the energy required by a Brownian implementation of Grover's algorithm. All that remains is to show that the latching energy is negligible. Indeed, we find that the energy required to suppress backwards transitions from the final state for a time of order t is $O\left(kT ln(t kT)\right) = O\left(\frac{N}{Mt}ln\left(\frac{N}{M}\right)\right)$. This is negligible as long as $M$ is at least logarithmic in $N$.

Thus, as with collision search, the quantum and classical preimage search algorithms appear to offer the same tradeoffs between time, energy , and memory:

\begin{equation} \label{Epreimage}
E_{cl} = E_{quant} = O \left(\frac{N}{t}\right).
\end{equation}

\section{Preimage Search at constant Power and Temperature / Energy Scale}\label{PandT}

In contrast to the collision search case, matching the time/ memory/ energy tradeoffs of Grover's algorithm with a classical search requires a somewhat unrealistic assumption. We assume that  if a computational process can be accomplished at a temperature $T$ in a time $t$, then an isomorphic computation can also be accomplished at a temperature $\alpha T$ in a time $\frac {T}{\alpha}$. This would be true if physics were scale invariant, but the physics of the real world is almost certainly not scale invariant. A more realistic model would therefore restrict the range of temperatures where a given computation is considered feasible. We will therefore repeat the analysis of the previous section assuming a fixed temperature $T$. For added realism, in addition to memory $M$, and time $t$, we will express the resources required for search in terms of power, $P = \frac{E}{t}$, rather than energy, since a fixed power budget is a more common limitation than a fixed energy budget.

From Equation~\ref{Epreimage} we find:

\[
N=O\left(Pt^2\right).
\]

Plugging this into Equation~\ref{Tpreimage} gives us:
\[
M=O\left(\frac{Pt}{T}\right).
\]

We can now calculate time and memory requirements in terms of $T$, $P$, and $N$:

\begin{align}\label{tpreimage}
t_{cl} = O\left(\sqrt{\frac{N}{P}}\right)\\
\label{Mpreimage}
M_{cl} = O\left(\frac{\sqrt{NP}}{T}\right)
\end{align}

A similar analysis may be done in the quantum case. Here we use Equation~\ref{TGrover} as a lower bound for $T$. If the per gate energy $\epsilon$ exceeds $kT$, we enter the thermodynamic regime of irreversible computing, as opposed to Brownian computing, at which point the time per gate not only fails to further decrease with increasing $\epsilon$, but must in fact increase to prevent the waste heat from heating the computing system to a temperature higher than $T$. Combining this bound with equation~\ref{EGrover} then yields the following time and memory requirements for Grover search at fixed power and temperature:

\begin{align}\label{tGrover}
t_{quant} = O\left(\sqrt{\frac{N}{P}}\right)\\
\label{MGrover}
M_{quant} = O\left(\frac{P}{T^2}\right)
\end{align}

Thus we find, fixing power and temperature, that our classical search strategy recovers the squareroot time scaling of Grover's algorithm. However, unlike Grover's algorithm, whose space requirement is determined only by the power budget and maximum operating temperature, the classical algorithm also requires memory that scales, like the time, with the squareroot of the size of the search space.

\section{Factors associated with the cost of oracle queries}
The asymptotic complexities given in previous sections ignore the computational complexity of individual oracle queries. Most of the results of previous sections remain substantively similar if these factors are included. We will model each oracle query as a circuit with depth $d_0$, width $m_0$, and total gates $g_0$.

In the case of powered Brownian computation, the effect of these factors is fairly straightforward. The memory imposed limit on paralleism (and number of table entries in the case of BHT) is now $p_{max} = O\left(\frac{M}{m_0}\right)$. Likewise, if $t_0$ is the time per query required to complete the computation in time $t$, we will now require an energy per gate of $\epsilon = O\left(\frac{d_0}{t_0}\right)$. We must also ensure that all the bits or qubits in the circuit advance through it roughly synchronously. This can be done, for example, by associating a clock state of size $O\left(log(d_0)\right)$ to each bit or qubit in the oracle circuit, and imposing a restoring potential proportional to the squared difference of the clock states of neighboring qubits. This will tend to couple the clock states of nearby qubits, but will not dissipate any net energy. As with other energy barriers ensuring correct computation, this potential need only extend logarithmically far from the equilibrium point, relative to the total size of the computation. We will generally ignore the logarithmic memory cost of the clock state and the logarithmic computational costs associated with creating interactions between the clock state, but in more detailed models, they may be subsumed into $m_0$ and $g_0$ respectively. Finally, we must take into account the number of gates required to perform an oracle query, $g_0$. Making these substitutions into equations~\ref{EBHT}, and \ref{EVOW} gives the following energy costs for quantum and classical collision search:

\begin{equation}\label{EBHTfull}
E_{quant} = O\left(p \cdot  g_0\sqrt{\frac{m_0N}{Mp}} \cdot d_0\frac{\sqrt{\frac{m_0N}{Mp}}}{t} \right) = O\left(\frac{g_0m_0d_0N}{Mt} \right);
\end{equation}

\begin{equation}\label{EVOWfull}
E_{cl} = O\left(\frac{M}{m_0} \cdot g_0\frac{m_0\sqrt{N}}{M} \cdot \frac{m_0d_0\sqrt{N}}{Mt} \right) = O\left(\frac{g_0m_0d_0N}{Mt} \right).
\end{equation}

Again, we find the classical and quantum complexities to be identical. In both cases, the useful memory size is bounded above by $O\left(m_0\sqrt{N}\right)$.

Similarly, we may make the same substitutions in equations~\ref{TGrover} and \ref{EGrover} to include these factors in the per gate and total energy cost Grover search:

\begin{equation}\label{TGroverfull}
\epsilon_{quant} = O\left(\frac{d_0\sqrt{\frac{m_0N}{M}}}{t} \right);
\end{equation}

\begin{equation}\label{EGroverfull}
E_{quant} = O\left(\frac{M}{m_0} \cdot g_0\sqrt{\frac{m_0N}{M}} \cdot \frac{d_0\sqrt{\frac{m_0N}{M}}}{t} \right) = O\left(\frac{g_0d_0N}{t}\right).
\end{equation}

In the case of unpowered Brownian computation, we must calculate the temperature $T$ required for random Brownian motion to power the traversal of an oracle circuit of depth $d_0$ and containing $g_0$ gates in time $t_0$. To do this, we create a random variable, $x$ indicating the total number of gates that have been completed at a time $t$. We expect that $x$ will obey the usual formula for Brownian motion, $\langle x^2 \rangle = Dt$, for some $D$, which will depend on $T$, $g_0,$ and $d_0$. We will then require $Dt_0 = O\left(g_0^2\right)$. It remains to determine the scaling of $D$: Note that at any given time, on average $O\left(\frac{g_0}{d_0}\right)$ gates will be exposed to activation by thermal noise. (The remaining gates will be disallowed by the clock states associated with their input/output bits.) Each of these gates is expected to contribute $O(Tdt)$ to $d\langle x^2\rangle$. The coupling potential between neighboring clock states will also drive the activation of individual gates, but it should have no net effect on $x$, since every gate driven forward by the couplining potential will be counterbalanced by another gate driven backwards. Thus we find that $D = O\left(\frac{Tg_0}{d_0}\right)$ and therefore $T = O\left(\frac{g_0d_0}{t_0}\right)$.

We may now apply this analysis to equations~\ref{Tpreimage} and \ref{Epreimage}. Since, in order to complete a preimage search of size $N$ in time, $t$ with memory $M$, we need $t_0 = \frac{m_0N}{Mt}$, we find that:

\begin{equation}\label{Tpreimagefull}
T_{cl} = O\left(\frac{g_0m_0d_0N}{Mt}\right),
\end{equation}

and,

\begin{equation}\label{Epreimagefull}
E_{cl} = O\left(M \cdot \frac{g_0m_0d_0N}{Mt}\right) =  O\left(\frac{g_0m_0d_0N}{t}\right) = O\left(m_0 E_{quant}\right).
\end{equation}

Note that, when we include cost factors associated with the size and computational complexity of oracle queries, the mostly unpowered randomized preimage search is more energy intensive than Grover's algorithm by a factor of $O(m_0)$. Nonetheless, this factor is generally expected to be logarithmic in $N$ and may easily be overwhelmed by the various costs associated with implementing fault tolerant quantum computation. We may also consider the fixed power and temperature scenario discussed in section \ref{PandT}. In this case, equations~\ref{tpreimage}, \ref{Mpreimage}, \ref{tGrover}, and \ref{MGrover} become:

\begin{align}
t_{cl} = O\left(\sqrt{\frac{g_0m_0d_0N}{P}}\right)\\
M_{cl} = O\left(\frac{\sqrt{g_0m_0d_0NP}}{T}\right)
\end{align}

\begin{align}
t_{quant} = O\left(\sqrt{\frac{g_0d_0N}{P}}\right)\\
M_{quant} = O\left(\frac{m_0d_0P}{g_0T^2}\right)
\end{align}

\section{Conclusion}





% ===========================================================================
\bibliographystyle{splncs}
\bibliography{References}
\end{document}
